#define _CRT_SECURE_NO_WARNINGS

#include<vector>
#include<string>
using namespace std;

namespace myhash
{
	template<class K, class V>
	struct Node
	{
		pair<K, V> _data;
		Node<K, V>* _next;

		Node(const pair<K, V>& data = make_pair(K(), V()))
			:_data(data)
			,_next(nullptr)
		{}
	};


	template<class T>
	struct round
	{
		size_t operator()(const T& key)
		{
			return (size_t)key;
		}
	};

	template<>
	struct round<string>
	{
		size_t operator()(const string& key)
		{
			size_t hash = 0;
			for (auto e : key)
			{
				hash *= 31;
				hash += e;
			}

			return hash;
		}
	};

	template<class K, class V, class Hash = round<K>, class Pred = equal_to<K>>
	class hash
	{
		typedef Node<K, V> Node;
	public:
		hash(size_t size = 13)
		{
			_hash.resize(size,nullptr);
			_size = 0;
		}
		hash(const hash& obj)
		{
			_hash.resize(obj._hash.size());
			_size = obj._size;
			for (int i = 0; i < obj._hash.size(); i++)
			{
				if (obj._hash[i])
				{
					Node* cur = obj._hash[i];
					Node* prev = nullptr;
					while (cur)
					{
						Node* newnode = new Node(cur->_data);
						if (prev)
							prev->_next = newnode;
						prev = newnode;
						cur = cur->_next;
						if (_hash[i] == nullptr)
							_hash[i] = newnode;
					}
				}
			}
		}
		hash& operator=(hash obj)
		{
			swap(obj);
			return *this;
		}
		~hash()
		{
			for (int i = 0; i < _hash.size(); i++)
			{
				if (_hash[i])
				{
					Node* cur = _hash[i];
					while (cur)
					{
						Node* next = cur->_next;
						delete cur;
						cur = next;
					}
					_hash[i] = nullptr;
				}
			}
		}
		void swap(hash& obj)
		{
			_hash.swap(obj._hash);
			std::swap(_size, obj._size);
		}
		bool insert(const pair<K, V>& data)
		{
			if (find(data.first) != nullptr)
				return false;

			double load = (double)_size / _hash.size();
			
			if (load >= 1.0)
			{
				hash tmp(_hash.size()*2.5);
				
				for (int i = 0; i < _hash.size(); i++)
				{
					if (_hash[i])
					{
						Node* cur = _hash[i];
						while (cur)
						{
							Hash ha;
							size_t keyi = ha(cur->_data.first) % (tmp._hash.size());

							tmp._size++;

							Node* next = cur->_next;

							cur->_next =tmp._hash[keyi];
							tmp._hash[keyi] = cur;

							cur = next;
						}
						_hash[i] = nullptr;
					}
				}
				swap(tmp);
			}

			Hash ha;
			size_t keyi = ha(data.first) % (_hash.size());
			
			Node* newnode = new Node(data);

			newnode->_next = _hash[keyi];
			_hash[keyi] = newnode;


			_size++;

			return true;
		}
		bool erase(const K& key)
		{
			Hash ha;
			size_t keyi = ha(key) % (_hash.size());
			Pred pred;
			Node* cur = _hash[keyi];
			Node* prev = nullptr;
			while (cur)
			{
				if (pred(cur->_data.first, key))
				{
					if (prev == nullptr)
					{
						_hash[keyi] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}
					delete cur;
					_size--;
					return true;
				}
				prev = cur;
				cur = cur->_next;
			}
			return false;
		}
		pair<K,V>* find(const K& key)
		{
			Hash ha;
			size_t keyi = ha(key) % (_hash.size());
			Pred pred;
			Node* cur = _hash[keyi];
			while (cur)
			{
				if (pred(cur->_data.first, key))
				{
					return &cur->_data;
				}
				cur = cur->_next;
			}
			return nullptr;
		}
		bool empty()const
		{
			return _size == 0;
		}
		size_t size()const
		{
			return _size;
		}
	private:
		vector<Node*>_hash;
		size_t _size;
	};
}